package 数据结构练习;

import java.util.LinkedList;
import java.util.Queue;

public class 基数排序 {
    public static void main(String[] args) {
        int a[] = new int[]{15,29,1996,47,53,13,28,44,187,65,55,42,17,5};
        //先取得所有数中最大数的位数
        int digit = getDigit(a);
        //排序
        sort(a,digit);
        //打印
        for(int x:a){
            System.out.print(x+" ");
        }
    }

    //先取得所有数中最大数的位数
    public static int getDigit(int[] a){
        int digit = 1;
        for(int x:a){
            if(x/Math.pow(10,digit) > 0){
                x = (int) (x/Math.pow(10,digit));
                while (x>0){
                    x = x/10;
                    digit++;
                }
            }
        }
        return digit;
    }

    //排序
    public static void sort(int[] a,int digit){
        //这里递归，从低位向高位排序
        if(digit>1){
            sort(a,digit-1);
        }
        //申请10个队列，并初始化
        Queue<Integer>[] queues = new Queue[10];
        for(int i=0;i<queues.length;i++){
            queues[i] = new LinkedList<>();
        }
        int point = 0;
        for (int i=0;i<a.length;i++){
            int n = (int) (a[i]/Math.pow(10,digit-1));
            //不够这么多位的直接送到0队列
            if(n == 0){
                queues[0].add(a[i]);
            }
            //够位数的
            else {
                int n2 = (int) (a[i]/Math.pow(10,digit-1));
                queues[n2%10].add(a[i]);
            }
        }
        //将队列中的数依次全部取出来，放进数组
        for(int i=0;i<10;i++){
            while (!queues[i].isEmpty()){
                a[point] = queues[i].remove();
                point++;
            }
        }
    }
}
